package main

//#link；https://leetcode-cn.com/problems/house-robber-iii/
import (
	"fmt"
	. "whoops/leetcode/common"
)

func main() {
	//node := TreeNode{}
}

//打家劫舍的基础上换成了二叉树 偷了根节点，则左右节点不能偷，偷了左右节点则根节点不能偷
func rob(root *TreeNode) int {
	result := dfs(root)
	return max(result[0], result[1])
}

//dp[i] dp[0]表示选中，dp[1]表示不选中
func dfs(node *TreeNode) []int {
	if node == nil {
		return []int{0, 0}
	}
	l, r := dfs(node.Left), dfs(node.Right)
	//若当前节点选中，则最大值为左右节点不选中
	selected := node.Val + l[1] + r[1]
	unSelected := max(l[0], l[1]) + max(r[0], r[1])
	return []int{selected, unSelected}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
